package a3_p04_ak_fh;

import java.util.HashSet;
import java.util.Set;

import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.util.UnionFind;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedMultigraph;
import org.jgrapht.util.FibonacciHeap;
import org.jgrapht.util.FibonacciHeapNode;

import a2_p04_ak_fh.AttVertex;
import a2_p04_ak_fh.Dijkstra;

public class Kruskal {
	
	private WeightedGraph<AttVertex, DefaultWeightedEdge> mingraph = new WeightedMultigraph<AttVertex, DefaultWeightedEdge>(
			DefaultWeightedEdge.class);
	private long time = 0;
	private int hits = 0;
	private double weightsum = 0.0;
	
	private Kruskal(WeightedGraph<AttVertex, DefaultWeightedEdge> graph,boolean fib){
		this.mingraph = CalcGraph(graph, fib);
	}
	
	public WeightedGraph<AttVertex, DefaultWeightedEdge> getGraph(){
		return this.mingraph;
	}
	
	public long getTimeInMillis(){
		return this.time;
	}
	public long getTimeInSec(){
		return this.time/100;
	}
	public int getHits(){
		return this.hits;
	}
	
	public double getWeightSum(){
		return this.weightsum;
	}
	
	public static Kruskal CalcPriQu(WeightedGraph<AttVertex, DefaultWeightedEdge> graph){
		return new Kruskal(graph,false);
	}
	
	public static Kruskal CalcFibHeap(WeightedGraph<AttVertex, DefaultWeightedEdge> graph){
		return new Kruskal(graph,true);
	}
	private WeightedGraph<AttVertex, DefaultWeightedEdge> CalcGraph(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,boolean fib) {
		
		WeightedGraph<AttVertex, DefaultWeightedEdge> mingraph = new WeightedMultigraph<AttVertex, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);

		
		Set<DefaultWeightedEdge> allEdges = new HashSet<DefaultWeightedEdge>();
		FibonacciHeap<DefaultWeightedEdge> fibheap = new FibonacciHeap<DefaultWeightedEdge>();
		
		allEdges=graph.edgeSet();
		DefaultWeightedEdge edge = new DefaultWeightedEdge();
		DefaultWeightedEdge tmp,tmp2 = null;
		DefaultWeightedEdge[] sortedEdges = new DefaultWeightedEdge[allEdges.size()];
		UnionFind<AttVertex> vertices = new UnionFind<AttVertex>(graph.vertexSet());

		
		int queuelength = 0;
		
		
		boolean set = false;
		this.time = System.currentTimeMillis();
		if(!fib){
			
		//Build queue
		for (DefaultWeightedEdge ae : allEdges) {

			// Fuer das erste Element
			if (sortedEdges[0] == null) {
				sortedEdges[0] = ae;
			} else {
				//Gegebenfalls ueber das komplette Array iterieren
				for (int i = 0; i < sortedEdges.length; i++) {
					tmp = sortedEdges[i];
					//Erster freier Platz
					if(!set && sortedEdges[i] == null){
						sortedEdges[i]=ae;
						set=true;
					//Verschieben wenn momentaner kleiner als vorhandener
					}else if ((graph.getEdgeWeight(ae) < graph.getEdgeWeight(tmp))) {
						tmp = ae;
						//solange schieben bis naechster freier Platz belegt
						for (int j = i; j < sortedEdges.length; j++) {
							tmp2 = sortedEdges[j];
							sortedEdges[j] = tmp;
							tmp= tmp2;
							//Freier Platz gefunden
							if(tmp2==null){
								break;
							}
						}
						set=true;
						break;
						
					}

				}
			}
			set=false;
		}
		queuelength = sortedEdges.length;
		}else{
			//Build queue
			for (DefaultWeightedEdge ae : allEdges) {
				fibheap.insert(new FibonacciHeapNode<DefaultWeightedEdge>(ae), graph.getEdgeWeight(ae));
			}
			queuelength = fibheap.size();
		}

		for (int i = 0; i < queuelength; i++) {
			if(!fib){
				edge = sortedEdges[i];
			}else{
				FibonacciHeapNode<DefaultWeightedEdge> fbn = fibheap.removeMin();
				edge = fbn.getData();
			}
			AttVertex sourceVertex = new AttVertex(graph.getEdgeSource(edge).getName(),0);
			AttVertex targetVertex = new AttVertex(graph.getEdgeTarget(edge).getName(),0);
			this.hits++;
			if (!(vertices.find(sourceVertex).equals(vertices.find(targetVertex)))) {
                
            

				mingraph.addVertex(sourceVertex);
				mingraph.addVertex(targetVertex);

				// Add edge
				DefaultWeightedEdge newedge = new DefaultWeightedEdge();

				// Add Weight
				newedge = mingraph.addEdge(sourceVertex, targetVertex);
				
				mingraph.setEdgeWeight(newedge, graph.getEdgeWeight(edge));
				vertices.union(sourceVertex, targetVertex);
				this.weightsum += graph.getEdgeWeight(edge);
				
			}
		}
		this.time = System.currentTimeMillis()-this.time;
		System.out.println("Kantengewichtssumme: "+this.weightsum);
		System.out.println("Zugriffe: "+this.hits);
		System.out.println("Zeit[sec]: "+this.getTimeInSec());
		System.out.println("Zeit[msec]: "+this.getTimeInMillis());
		return mingraph;
	}
}
